/*
 *https://leetcode.cn/problems/time-needed-to-inform-all-employees/description/

*/

-------------------------------------------------------------------
class Solution {
public:
    int times = 0; // 用来记录传递消息所需的最大时间

    /**
     * 深度优先搜索函数，用于遍历组织结构并计算最大通知时间。
     *
     * @param mp 邻接表表示的组织结构图
     * @param informTime 通知每个员工所需的时间
     * @param vis 记录节点是否已经被访问过的布尔向量
     * @param time 当前累积的通知时间
     * @param i 当前处理的员工编号
     */
    void dfs(vector<vector<int>> &mp, vector<int>& informTime, vector<bool> &vis, int time, int i) {
        vis[i] = true; // 标记当前节点为已访问
        if (times < time) {
            times = time; // 更新最大通知时间
        }
        // 遍历当前员工的所有直接下属
        for (auto j : mp[i]) {
            if (!vis[j]) { // 如果下属还未被访问，则递归调用dfs
                dfs(mp, informTime, vis, time + informTime[i], j); // 累加通知时间，并继续向下遍历
            }
        }
    }

    /**
     * 计算将消息从最高管理层传递到所有员工所需的总时间。
     *
     * @param n 员工总数
     * @param headID 最高管理层的员工编号
     * @param manager 每个员工的直接上级的列表，如果该员工是最高管理层，则值为 -1
     * @param informTime 通知每个员工所需的时间
     * @return 将消息传递给所有员工所需的最长时间
     */
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<vector<int>> mp(n); // 创建邻接表表示的组织结构图
        for (int i = 0; i < n; ++i) {
            if (i != headID) {
                mp[manager[i]].push_back(i); // 构建图，将每个员工添加到其直接上级的下属列表中
            }
        }
        vector<bool> vis(n, false); // 初始化访问标记向量
        dfs(mp, informTime, vis, informTime[headID], headID); // 从最高管理层开始进行深度优先搜索
        return times; // 返回计算得到的最大通知时间
    }
};